Economics Dictionary of ArgumentsHome
| |||
|
| |||
| Minimax algorithm: The minimax algorithm is a recursive algorithm for choosing the next move in a two-player game. It works by recursively considering all possible moves that the player and their opponent can make, and then choosing the move that leads to the best outcome for the player. See also Artificial intelligence, Game theory, Strategies._____________Annotation: The above characterizations of concepts are neither definitions nor exhausting presentations of problems related to them. Instead, they are intended to give a short introduction to the contributions below. – Lexicon of Arguments. | |||
| Author | Concept | Summary/Quotes | Sources |
|---|---|---|---|
|
Stuart J. Russell on Minimax Algorithm - Dictionary of Arguments
Norvig I 164 Minimax Algorithm/gaming/Norvig/Russell: The minimax value of a node is the utility (for MAX) of being in the corresponding state, assuming that both players play optimally from there to the end of the game. Norvig I 165 The minimax algorithm (…) computes the minimax decision from the current state. It uses a simple recursive computation of the minimax values of each successor state, directly implementing the defining equations. The recursion proceeds all the way down to the leaves of the tree, and then the minimax values are backed up through the tree as the recursion unwinds. The minimax algorithm performs a complete depth-first exploration of the game tree. For real games, of course, the time cost is totally impractical, but this algorithm serves as the basis for the mathematical analysis of games and for more practical algorithms. Norvig I 167 The problem with minimax search is that the number of game states it has to examine is exponential in the depth of the tree. Unfortunately, we can’t eliminate the exponent, but it turns out we can effectively cut it in half. The trick is that it is possible to compute the correct minimax decision without looking at every node in the game tree. Solution: alpha–beta pruning. When applied to a standard minimax tree, it returns the same move as minimax would, but prunes away branches that cannot possibly influence the final decision. The general principle is this: consider a node n Norvig I 168 somewhere in the tree (...), such that Player has a choice of moving to that node. If Player has a better choice m either at the parent node of n or at any choice point further up, then n will never be reached in actual play. So once we have found out enough about n (by examining some of its descendants) to reach this conclusion, we can prune it. Norvig I 190 The minimax algorithm is traced to a 1912 paper by Ernst Zermelo(1), the developer of modern set theory. The paper unfortunately contained several errors and did not describe minimax correctly. On the other hand, it did lay out the ideas of retrograde analysis and proposed (but did not prove) what became known as Zermelo’s theorem: that chess is determined - White can force a win or Black can or it is a draw; we just don’t know which. Zermelo says that should we eventually know, “Chess would of course lose the character of a game at all.” A solid foundation for game theory was developed in the seminal work Theory of Games and Economic Behavior (von Neumann and Morgenstern, 1944)(2), which included an analysis showing that some games require strategies that are randomized (or otherwise unpredictable). Norvig I 191 VsMinimax algorithms: D. F. Beal (1980)(3) and Dana Nau (1980(4), 1983(5)) studied the weaknesses of minimax applied to approximate evaluations. They showed that under certain assumptions about the distribution of leaf values in the tree, minimaxing can yield values at the root that are actually less reliable than the direct use of the evaluation function itself. >Computer Games/Norvig. 1. Zermelo, E. (1913). Über Eine Anwendung der Mengenlehre auf die Theorie des Schachspiels. In Proc. Fifth International Congress of Mathematicians, Vol. 2, pp. 501–504 2. von Neumann, J. and Morgenstern, O. (1944). Theory of Games and Economic Behavior (first edition). Princeton University Press 3. Beal, D. F. (1980). An analysis of minimax. In Clarke, M. R. B. (Ed.), Advances in Computer Chess 2, pp. 103–109. Edinburgh University Press 4. Nau, D. S. (1980). Pathology on game trees: A summary of results. In AAAI-80, pp. 102–104. 5. Nau, D. S. (1983). Pathology on game trees revisited, and an alternative to minimaxing. AIJ, 21(1–2), 221–244._____________Explanation of symbols: Roman numerals indicate the source, arabic numerals indicate the page number. The corresponding books are indicated on the right hand side. ((s)…): Comment by the sender of the contribution. Translations: Dictionary of Arguments The note [Concept/Author], [Author1]Vs[Author2] or [Author]Vs[term] resp. "problem:"/"solution:", "old:"/"new:" and "thesis:" is an addition from the Dictionary of Arguments. If a German edition is specified, the page numbers refer to this edition. |
Russell I B. Russell/A.N. Whitehead Principia Mathematica Frankfurt 1986 Russell II B. Russell The ABC of Relativity, London 1958, 1969 German Edition: Das ABC der Relativitätstheorie Frankfurt 1989 Russell IV B. Russell The Problems of Philosophy, Oxford 1912 German Edition: Probleme der Philosophie Frankfurt 1967 Russell VI B. Russell "The Philosophy of Logical Atomism", in: B. Russell, Logic and KNowledge, ed. R. Ch. Marsh, London 1956, pp. 200-202 German Edition: Die Philosophie des logischen Atomismus In Eigennamen, U. Wolf (Hg), Frankfurt 1993 Russell VII B. Russell On the Nature of Truth and Falsehood, in: B. Russell, The Problems of Philosophy, Oxford 1912 - Dt. "Wahrheit und Falschheit" In Wahrheitstheorien, G. Skirbekk (Hg), Frankfurt 1996 Norvig I Peter Norvig Stuart J. Russell Artificial Intelligence: A Modern Approach Upper Saddle River, NJ 2010 |
||
> Counter arguments against Russell
> Counter arguments in relation to Minimax Algorithm
